package String.easy;


/**
 * 1. 问题描述
 *      我们来定义一个函数f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。
 *      例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。
 *      现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i]
 *      是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。

 * 2. 算法分析
 *      首先理解题意：题目的要求是求一个长度为queries.length长度的整形数组 answer[]
 *          answer[i]中的值满足如下要求：f(queries[i]) < min f(w) | w in words
 *
 *      最简单的想法：定义一个numSmallerCharInString(String s)方法,该方法的目的是计算出字符串中的按照字典排序法最小的字符串的次数
 *      第一步我们先遍历words中的所有单词，利用上述的函数计算出每个单词的按照字典排序的最小字符的次数，作为参照
 *      第二步我们遍历queries数组中的每一个单词，在遍历的过程中每遍历一个单词我们设置一个整形变量count用于记录当前
 *      字符按照定义的次数在temp数组中的那些元素下，如果小让count++，最终当前单词对应到answer的值，整体想法就是穷举的思想
 *      时间复杂度和空间复杂度都高
 *
 *      优化上述算法：
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 比较字符串中最小字符的出现次数 {
    public static void main(String[] args) {
        String[] queries = {"bbb","cc"};
        String[] words = {"a","aa","aaa","aaaa"};
        for (int i : numSmallerByFrequency(queries, words)) {
            System.out.println(i);
        }
    }
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] temp = new int[words.length];
        for (int i = 0; i < words.length; i++) { // 计算出words中每个单词的字典序最小的字符的个数
            temp[i] = numSmallerCharInString(words[i]);
        }
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int count = 0;
            for (int c : temp) {
                if (numSmallerCharInString(queries[i]) < c) {
                    count++;
                }
            }
            answer[i] = count;
        }
        return answer;
    }

    /**
     * 计算出字符串中的按照字典排序法最小的字符串的次数
     * @param words
     * @return
     */
    public static int numSmallerCharInString(String words) {
        int[] counts = new int[26];
        for (int i = 0; i < words.length(); i++) { ;
            counts[words.charAt(i) - 'a']++; // 计算出当前字符在26个字母中的位置
        }
        int res = 0;
        for (int count : counts) {
            if (count != 0) {
                res = count;
                break;
            }
        }
        return res;
    }


}
